package com.future;

/**
 * Description: �����п��Բ�����
 * ����һ���������� nums ���ҵ�������ϸ���������еĳ��ȡ�
 * <p>
 * ������?���������������������У�ɾ������ɾ���������е�Ԫ�ض����ı�����Ԫ�ص�˳�����磬[3,6,2,7] ������ [0,3,1,6,2,2,7] �������С�
 * <p>
 * ?
 * ʾ�� 1��
 * <p>
 * ���룺nums = [10,9,2,5,3,7,101,18]
 * �����4
 * ���ͣ�������������� [2,3,7,101]����˳���Ϊ 4 ��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/longest-increasing-subsequence
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/3/30 09:38
 */
public class Solution_300 {

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        nums = new int[]{0, 1, 0, 3, 2, 3};
        nums = new int[]{4, 10, 4, 3, 8, 9};
       // nums = new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6};
        System.out.println(lengthOfLIS(nums));
        System.out.println(lengthOfLIS_v2(nums));
    }

    /**
     * eg:{4, 10, 4, 3, 8, 9}
     * i=1ʱ��dp={1,2}
     * i=2ʱ��û�б�4��С�ģ�dp={1,1,1}
     * i=3ʱ��û�б�3��С�ģ�dp={1,1,1,1}
     * i=4ʱ����8��С����λ��0,2,3 ,���Ķ���1�������ڴ˻�����+1��dp={1,1,1,1,2}
     * i=5ʱ����9��С����λ��0,2,3,4������dpλ��4��ֵΪ2�������ڴ˻�����+1��dp={1,1,1,1,2,3}
     *
     * @param nums
     * @return
     */
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = 1;
        int N = nums.length;
        /**
         * ��Ŷ�Ӧnums�±��ֵ�������������
         */
        int[] dp = new int[N];
        dp[0] = 1;
        for (int i = 1; i < N; i++) {
            int max = 1;
            int curVal = nums[i];
            /**
             * ����dp�����ȵ�ǰֵС�����������������У�Ȼ���ڴ˻�����+1
             */
            for (int j = 0; j < i; j++) {
                if (nums[j] < curVal) {
                    max = Math.max(max, dp[j] + 1);
                }
            }
            ans = Math.max(ans, max);
            dp[i] = max;
        }
        return ans;
    }

    /**
     * ����Ҫ������Ҫ��
     * eg:arr={1, 3, 6, 7, 9, 4, 10, 5, 6}
     * --------0  1  2  3  4  5  6   7  8
     * ��ʼʱ��end[0]=arr[0]=1,R=0(R������Ϊ��end��Ч�ķ�Χ�ڵĳ���-1)
     * ���±�Ϊ1��ʼ����
     * i=1
     * ��0~0(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[1]С�����Ҳ�λ��+1���������±�Ϊ1������ֵΪend={1,3},R=1
     * i=2
     * ��0~1(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[2]С�����Ҳ�λ��+1���������±�Ϊ2������ֵΪend={1,3,6},R=2
     * i=3
     * ��0~2(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[3]С�����Ҳ�λ��+1���������±�Ϊ3������ֵΪend={1,3,6,7},R=3
     * i=4
     * ��0~3(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[4]С�����Ҳ�λ��+1���������±�Ϊ4������ֵΪend={1,3,6,7,9},R=4
     * i=5
     * ��0~4(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[5]=4С�����Ҳ�λ��+1���������±�Ϊ3������ֵΪend={1,3,4,7,9},R=4
     * i=6
     * ��0~4(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[6]=10С�����Ҳ�λ��+1���������±�Ϊ5������ֵΪend={1,3,4,7,9,10},R=5
     * i=7
     * ��0~5(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[7]=5С�����Ҳ�λ��+1���������±�Ϊ3������ֵΪend={1,3,4,5,9,10},R=5
     * i=8
     * ��0~5(��0~R)ͨ�����ֲ��ң���end�������ҵ���arr[8]=6С�����Ҳ�λ��+1���������±�Ϊ4������ֵΪend={1,3,4,5,6,10},R=5
     * ��ô�𰸾��� R+1;
     *
     * @param nums
     * @return
     */
    public static int lengthOfLIS_v2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        int R = 0;
        int[] end = new int[N];
        end[0] = nums[0];
        for (int i = 1; i < N; i++) {
            int l = 0;
            int r = R;
            while (l <= r) {
                int m = l + ((r - l) >> 1);
                if (end[m] < nums[i]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            end[l] = nums[i];
            R = Math.max(l, R);
        }
        return R + 1;
    }
}
